/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 二叉树的后序遍历
 * 递归和非递归
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月17日
 */
public class BinaryTreePostorderTraversal {
    //左、右、根
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root==null){
            return result;
        }
        postOrderTraversal(root, result);
        return result;
    }
    /**
     * 后序方法的递归遍历
     * @param root
     * @param result
     * @author towan
     * 2015年5月21日
     */
    public void postOrderTraversal(TreeNode root, List<Integer> result) {
        if(root!=null){
            postOrderTraversal(root.left,result);
            postOrderTraversal(root.right,result);
            result.add(root.val);
        }
    }
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode tleft = new TreeNode(8);
        TreeNode tright = new TreeNode(7);
        t1.left = tleft;
        t1.right = tright;
        
        tright.left = new TreeNode(3);
        tright.right = new TreeNode(8);
        
        tleft.left = new TreeNode(9);
        tleft.right = new TreeNode(2);
        
        BinaryTreePostorderTraversal postorderTraversalBinaryTree = new BinaryTreePostorderTraversal();
        List<Integer> list = postorderTraversalBinaryTree.postorderTraversal(t1);
        System.out.println(list);
    }
}
